Graph (গ্রাফ) হলো একটি গাণিতিক কনসেপ্ট যা সিস্টেমের বিভিন্ন উপাদান (যেমন, নোড বা ভারটিস) এবং তাদের মধ্যে সংযোগ (এজ) এর সম্পর্ককে বোঝায়। গ্রাফের মধ্যে বিভিন্ন ধরনের সম্পর্ক থাকতে পারে এবং এটি বিভিন্ন সমস্যা যেমন নেটওয়ার্কিং, সড়ক বা ট্রাফিক ম্যাপ, সোশ্যাল মিডিয়া সম্পর্ক ইত্যাদি মডেল করতে ব্যবহৃত হয়।
গ্রাফ রেপ্রেজেন্টেশনের দুইটি প্রধান পদ্ধতি হলো:
- Adjacency Matrix
- Adjacency List
আমরা এই দুটি পদ্ধতি জাভাতে কিভাবে ইমপ্লিমেন্ট করতে পারি তা দেখবো।
১. Adjacency Matrix (এডজেসেন্সি ম্যাট্রিক্স)
Adjacency Matrix একটি 2D অ্যারে দ্বারা গ্রাফের রেপ্রেজেন্টেশন। এই পদ্ধতিতে, গ্রাফের প্রতিটি নোডের জন্য একটি রো এবং কলাম তৈরি হয়, এবং এই রো কলামগুলোকে 1 বা 0 দিয়ে পূর্ণ করা হয়, যেখানে 1 নির্দেশ করে যে দুটি নোডের মধ্যে একটি এজ (Edge) রয়েছে, আর 0 নির্দেশ করে যে দুটি নোডের মধ্যে কোন এজ নেই।
Adjacency Matrix Representation
- 1: দুটি নোডের মধ্যে একটি এজ রয়েছে।
- 0: দুটি নোডের মধ্যে কোন এজ নেই।
উদাহরণ: Adjacency Matrix
ধরা যাক, আমাদের একটি গ্রাফ রয়েছে যেটিতে ৪টি নোড রয়েছে (A, B, C, D), এবং এজগুলি (A-B, A-C, B-D)।
A -- B
| |
C -- D
এই গ্রাফের জন্য অ্যাডজেসেন্সি ম্যাট্রিক্স হবে:
A B C D
A [0, 1, 1, 0]
B [1, 0, 0, 1]
C [1, 0, 0, 0]
D [0, 1, 0, 0]
এখানে, matrix[i][j] মানে হল, i এবং j নোডের মধ্যে একটি এজ আছে কিনা। যদি এজ থাকে তবে সেটি 1, না থাকলে 0।
Java তে Adjacency Matrix ইমপ্লিমেন্টেশন
public class GraphAdjMatrix {
private int[][] adjMatrix;
private int numVertices;
public GraphAdjMatrix(int numVertices) {
this.numVertices = numVertices;
adjMatrix = new int[numVertices][numVertices];
}
// Add edge between vertex v1 and v2
public void addEdge(int v1, int v2) {
adjMatrix[v1][v2] = 1;
adjMatrix[v2][v1] = 1; // Since it's an undirected graph
}
// Display the adjacency matrix
public void displayGraph() {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
System.out.print(adjMatrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
GraphAdjMatrix graph = new GraphAdjMatrix(4); // 4 vertices
graph.addEdge(0, 1); // Add edge between A and B
graph.addEdge(0, 2); // Add edge between A and C
graph.addEdge(1, 3); // Add edge between B and D
graph.displayGraph();
}
}
আউটপুট:
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
২. Adjacency List (এডজেসেন্সি লিস্ট)
Adjacency List হলো একটি গ্রাফের প্রতিটি নোডের জন্য একটি লিস্ট (বা লিঙ্কড লিস্ট) তৈরি করা, যা সংশ্লিষ্ট নোডগুলির সাথে সংযোগ সম্পর্কিত এজগুলিকে ধারণ করে। এটি সাধারণত ওরিয়েন্টেড অথবা আন্ডিরেক্টেড গ্রাফের জন্য ব্যবহৃত হয়। অ্যাডজেসেন্সি লিস্টে সাধারণত একটি অ্যারে বা লিস্ট থাকে, যেখানে প্রতিটি নোডের জন্য অন্য নোডের লিঙ্ক সংরক্ষিত থাকে।
Adjacency List Representation
- প্রতিটি নোডের জন্য একটি লিস্ট তৈরি করা হয় যা তার সাথে সংযুক্ত অন্যান্য নোডের নাম ধারণ করে।
উদাহরণ: Adjacency List
ধরা যাক, আমাদের একটি গ্রাফ রয়েছে যেটিতে ৪টি নোড রয়েছে (A, B, C, D), এবং এজগুলি (A-B, A-C, B-D)।
A -- B
| |
C -- D
এই গ্রাফের জন্য অ্যাডজেসেন্সি লিস্ট হবে:
A: B, C
B: A, D
C: A
D: B
Java তে Adjacency List ইমপ্লিমেন্টেশন
import java.util.*;
public class GraphAdjList {
private Map<Integer, List<Integer>> adjList;
private int numVertices;
public GraphAdjList(int numVertices) {
this.numVertices = numVertices;
adjList = new HashMap<>();
for (int i = 0; i < numVertices; i++) {
adjList.put(i, new LinkedList<>());
}
}
// Add edge between vertex v1 and v2
public void addEdge(int v1, int v2) {
adjList.get(v1).add(v2);
adjList.get(v2).add(v1); // Since it's an undirected graph
}
// Display the adjacency list
public void displayGraph() {
for (int i = 0; i < numVertices; i++) {
System.out.print(i + ": ");
for (Integer vertex : adjList.get(i)) {
System.out.print(vertex + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
GraphAdjList graph = new GraphAdjList(4); // 4 vertices
graph.addEdge(0, 1); // Add edge between A and B
graph.addEdge(0, 2); // Add edge between A and C
graph.addEdge(1, 3); // Add edge between B and D
graph.displayGraph();
}
}
আউটপুট:
0: 1 2
1: 0 3
2: 0
3: 1
সারাংশ
Adjacency Matrix এবং Adjacency List হলো গ্রাফ রিপ্রেজেন্টেশনের দুটি সাধারণ পদ্ধতি, প্রতিটির নিজস্ব সুবিধা এবং সীমাবদ্ধতা রয়েছে।
- Adjacency Matrix: গ্রাফের সকল সম্পর্ক একসাথে একটি 2D অ্যারেতে সংরক্ষিত থাকে। এটি সোজা এবং নির্দিষ্ট সাইজের গ্রাফের জন্য কার্যকরী, তবে বড় গ্রাফের ক্ষেত্রে মেমরি খরচ বেশি হয়।
- Adjacency List: এটি প্রতিটি নোডের জন্য একটি লিস্ট তৈরি করে যা তার সংযুক্ত নোডগুলির তালিকা সংরক্ষণ করে। এটি মেমরি ইফিশিয়েন্ট এবং অনেক বড় গ্রাফের জন্য উপযুক্ত।
এছাড়া, বিভিন্ন গ্রাফ অ্যালগরিদম (যেমন BFS, DFS, Dijkstra) কার্যকরীভাবে এই রিপ্রেজেন্টেশনগুলির উপর ভিত্তি করে কাজ করে।
Read more
